# 《零矩阵》
# 原题链接：https://leetcode.cn/leetbook/read/array-and-string/ciekh/

# 编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零。


#
class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        rowlen = len(matrix)
        collen = len(matrix[0])
        row, col = [], []
        for i in range(rowlen):
            for j in range(collen):
                if matrix[i][j] == 0:
                    row += [i]
                    col += [j]
        for i in row:
            for j in range(collen):
                matrix[i][j] = 0
        for j in col:
            for i in range(rowlen):
                matrix[i][j] = 0


# 优化
class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        m = len(matrix)
        n = len(matrix[0])
        row_zero = [1] * m
        col_zero = [1] * n
        # matrixDict = [[0 for i in range(n)] for j in range(m)]
        # 错误写法：matrixDict = [[0]*n]*m
        # 统计、记录行列为0的元素
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    # matrixDict[i][j] = 1
                    row_zero[i] = 0
                    col_zero[j] = 0
        # 置零
        for i in range(m):
            for j in range(n):
                if row_zero[i] == 0 or col_zero[j] == 0:
                    matrix[i][j] = 0


# 示例代码：
class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        zero_i = {}
        zero_j = {}
        n = len(matrix)
        m = len(matrix[0])
        for i in range(n):
            for j in range(m):
                if matrix[i][j] == 0:
                    if i not in zero_i:
                        zero_i[i] = 1
                    if j not in zero_j:
                        zero_j[j] = 1

        for i in range(n):
            for j in range(m):
                if i in zero_i or j in zero_j:
                    matrix[i][j] = 0
